package main.naiveBayes;

import java.io.File;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;

import y.base.Edge;
import y.base.EdgeCursor;
import y.base.EdgeList;
import y.base.EdgeMap;
import y.base.Node;
import y.base.NodeCursor;

import main.graph.FormTree;
import main.graph.FormTreeWithMapping;
import main.graph.GetCMGraph;
import main.graph.GraphAlgo;
import main.graph.ValuedGraph;
import main.model.Attribute;
import main.model.EdgeGivenPath;
import main.model.EdgePriors;
import main.model.Entity;
import main.model.NodeAndLabel;
import main.model.OntoEle;
import main.model.OntoNodePair;
import main.model.OntoPath;
import main.model.SteinerTree;
import main.model.SteinerTreePathEle;

/**
 * 
 * compute a set of candidate trees in the ontology graph as candidate mappings
 * Each candidate tree consists of a set of paths corresponding to the set of form tree edges.
 * Each form tree edge is specified as a pair of ontology nodes (elements).
 * 
 * @author YuanAn
 *
 */
public class GetCandidateOntoTree {
	
	//get a set of Steiner tree from the ontology graph from a given form tree.
	public static ArrayList<EdgeList> getOntoSteiners(FormTree tree, ValuedGraph cmg) {
		
		ArrayList<EdgeList> ans = new ArrayList<EdgeList>();
		
		try {
			
			EdgeMap weights = cmg.createEdgeMap();
			for(EdgeCursor ec = cmg.edges(); ec.ok(); ec.next()){
				Edge edge = ec.edge();
				weights.setDouble(edge, 1.0);
			}
			
			ArrayList<String> labels =  new ArrayList<String>();
			for(NodeCursor nc = tree.nodes(); nc.ok(); nc.next()){
				Node n = nc.node();
				String v = (String) tree.getNodeValue(n);
				labels.add(v);
			}
			
			
			ArrayList<ArrayList<Node>> fixedSet = FindCorrespondence.getFixedNodes(cmg, labels);
			
			for(ArrayList<Node> fixed: fixedSet){
				
				ArrayList<EdgeList> steiners = GraphAlgo.allSteinerTreesIntegrated(cmg, weights, fixed);
				
				ans.addAll(steiners);
				
			}
			
			
		} catch (Exception e) {
			e.printStackTrace();
		}
		
		return ans;
	}
	
	//get a set of Steiner tree from the ontology graph from a given form tree.
	//Using a string matching algorithm to identify a set of corresponding nodes in the ontology
	public static ArrayList<SteinerTree> getOntoSteinersWithMatchingCorrespondences(FormTree tree, ValuedGraph cmg) {
		
		ArrayList<SteinerTree> ans = new ArrayList<SteinerTree>();
		
		try {
			
			EdgeMap weights = cmg.createEdgeMap();
			for(EdgeCursor ec = cmg.edges(); ec.ok(); ec.next()){
				Edge edge = ec.edge();
				weights.setDouble(edge, 1.0);
			}
			
			ArrayList<String> labels =  new ArrayList<String>();
			for(NodeCursor nc = tree.nodes(); nc.ok(); nc.next()){
				Node n = nc.node();
				String v = (String) tree.getNodeValue(n);
				labels.add(v);
			}
			
			
			
			//a list of onto nodes and their corresponding tree labels
			ArrayList<ArrayList<NodeAndLabel>> fixedSet = FindCorrespondence.getFixedNoddAndLabels(cmg, labels);
			
			for(ArrayList<NodeAndLabel> fixedNodeAndLabel: fixedSet){
				
				//get a new form tree with edge to twoEndLabels
				FormTree newTree = getFormTreeWithTwoEndLabels(tree, fixedNodeAndLabel, cmg);
				
				//get the set of fixed nodes
				ArrayList<Node> fixed = getFixedOntoNodes(fixedNodeAndLabel);
				
				ArrayList<EdgeList> steiners = GraphAlgo.allSteinerTreesIntegrated(cmg, weights, fixed);
				
				for(EdgeList steiner: steiners){
					SteinerTree aSteinerTree = new SteinerTree();
					aSteinerTree.setSteiner(steiner);
					aSteinerTree.setFormTree(newTree);
					
					ans.add(aSteinerTree);
				}
				
			}
			
			
		} catch (Exception e) {
			e.printStackTrace();
		}
		
		return ans;
	}
	
	
	//get a new form tree with edge to twoEndLabels
	public static FormTree getFormTreeWithTwoEndLabels(FormTree tree, ArrayList<NodeAndLabel> fixedNodeAndLabel,
			ValuedGraph cmg){
		
		FormTree ans = tree.duplicateFormTree();
		
		for(EdgeCursor ec = ans.edges(); ec.ok(); ec.next()){
			Edge e = ec.edge();
			
			//a new pair of labels
			ArrayList<String> endLabels = new ArrayList<String>();
			
			Node firstNode = e.source();
			Node secondNode = e.target();
			
			String firstNodeString = (String) ans.getNodeValue(firstNode);
			String secondNodeString = (String) ans.getNodeValue(secondNode);
			
			String firstNodeOntoLabel = getNodeOntoLabel(fixedNodeAndLabel, firstNodeString, cmg);
			String secondNodeOntoLabel = getNodeOntoLabel(fixedNodeAndLabel, secondNodeString, cmg);
			
			endLabels.add(firstNodeOntoLabel);
			endLabels.add(secondNodeOntoLabel);
			
			ans.putEdgeToTwoNodeLabels(e, endLabels);
		}
				
		
		return ans;
		
	}
	
	//find the corresponding node label according to the given node string 
	public static String getNodeOntoLabel(ArrayList<NodeAndLabel> fixedNodeAndLabel, 
			String nodeString, ValuedGraph cmg){
		
		for(NodeAndLabel nodeLabel: fixedNodeAndLabel){
			
			if(nodeLabel.getLabel().equalsIgnoreCase(nodeString)){
				Node node = nodeLabel.getNode();
				OntoEle ontoEle = (OntoEle) cmg.getNodeValue(node);
				return ontoEle.getName();
			}
		}
	
		return null;
	}
	
	//get the set of fixed nodes
	public static ArrayList<Node> getFixedOntoNodes(ArrayList<NodeAndLabel> fixedNodeAndLabel){
		
		ArrayList<Node> ans = new ArrayList<Node>();
		
		for(NodeAndLabel nodeLabel: fixedNodeAndLabel){
			ans.add(nodeLabel.getNode());
		}
		
		return ans;
	}
	
	/**
	 * return a set of paths in the Steiner tree corresponding to the edges in the form tree
	 * 
	 * @param tree
	 * @param steiner
	 * @param cmg
	 * @return
	 */
	public static HashMap<ArrayList<String>, OntoPath> getPathsFromSteiner(FormTree tree, EdgeList steiner, ValuedGraph cmg){
		
		//System.out.println("GetCandidateOntoTree:getPathsFromSteiner");
		
		HashMap<ArrayList<String>, OntoPath> ans = new HashMap<ArrayList<String>, OntoPath>();
		
		//for each ontoNodePair corresponding to an edge in the form tree, retrieve 
		//the corresponding path in the Steiner tree
		for(EdgeCursor ec = tree.edges(); ec.ok(); ec.next()){
			
			Edge treeEdge = ec.edge();
			
			//System.out.println((String) tree.getEdgeValue(treeEdge));
			
			ArrayList<String> nodePair = tree.getTwoEndLabels(treeEdge);
			
			String firstNodeLabel = nodePair.get(0);
			String secondNodeLabel = nodePair.get(1);
			
			EdgeList pathEdges = getCorrespondingPath(firstNodeLabel, secondNodeLabel, steiner, cmg);
			
			OntoPath path = new OntoPath();
			for(EdgeCursor pec = pathEdges.edges(); pec.ok(); pec.next()){
				Edge pathEdge = pec.edge();
				path.addEdge(pathEdge);
			}
				
			ans.put(nodePair, path);
		}
		
		
		return ans;
	}
	
	/**
	 * find the path corresponding to the two given end nodes
	 * 
	 * @param firstNode
	 * @param secondNode
	 * @param steiner
	 * @return
	 */
	public static EdgeList getCorrespondingPath(String firstNodeLabel, String secondNodeLabel, EdgeList steiner, 
			ValuedGraph cmg){
		
		//System.out.println("GetCandidateOntoTree:getCorrespondingPath");
		
		//make the starting node as a SteinerTreePathEle
		SteinerTreePathEle firstTreePathEle = new SteinerTreePathEle(firstNodeLabel, null, null);
		
		//a queue for BSF
		LinkedList<SteinerTreePathEle> queue = new LinkedList<SteinerTreePathEle>();
		
		queue.add(firstTreePathEle);
		
		ArrayList<Edge> visited = new ArrayList<Edge>(); //hold visited edges
		
		SteinerTreePathEle lastTreePathEle = null; //the element corresponding to secondNode
		
		while(!queue.isEmpty()){
			
			SteinerTreePathEle head = queue.removeFirst();
			
			String headNodeLabel = head.getCurrentNode();
			
			//get the set of edges that are incident to the firstnode in the steiner tree
			ArrayList<Edge> incidentEdges = getIncidentEdges(headNodeLabel, steiner, cmg);
			
			for(Edge incidentEdge: incidentEdges){
				//BSF each edge
				if(!visited.contains(incidentEdge)){
					//not visited yet
					visited.add(incidentEdge);
					
					Node headNode = getNodeCorrespondingLabel(incidentEdge, headNodeLabel, cmg);
					
					Node incidentOtherNode = incidentEdge.opposite(headNode);
					
					OntoEle incidentOtherNodeEle = (OntoEle)cmg.getNodeValue(incidentOtherNode);
					
					String incidentOtherNodeLabel = incidentOtherNodeEle.getName();
					
					if(incidentOtherNodeLabel.equalsIgnoreCase(secondNodeLabel)){
						//found the path
						lastTreePathEle = new SteinerTreePathEle(incidentOtherNodeLabel, incidentEdge, head);
						break;
					}
					else{//add a new element to the queue
						SteinerTreePathEle aEle = new SteinerTreePathEle(incidentOtherNodeLabel, incidentEdge, head);
						queue.add(aEle);
					}
				}
			}
		}//while !queue.isEmpty()
		
		EdgeList ans = new EdgeList();
		
		while(lastTreePathEle != null){
			//there is a previous edge leading to the current node
			Edge leadingEdge = lastTreePathEle.getIncidentEdge();
			if(leadingEdge != null)
				ans.add(0, leadingEdge);//add the leading edge at the head of the list
			
			lastTreePathEle = lastTreePathEle.getPreviousElement();
		}
					
		return ans;
		
	}
	
	//get the set of edges that are incident to the given headNode in the steiner tree
	public static ArrayList<Edge> getIncidentEdges(String headNodeLabel, EdgeList steiner, ValuedGraph cmg){
		
		//System.out.println("GetCandidateOntoTree:getIncidentEdges");
		
		ArrayList<Edge> ans = new ArrayList<Edge>();
		
		for(EdgeCursor ec = steiner.edges(); ec.ok(); ec.next()){
			
			Edge e = ec.edge();
			
			Node source = e.source();
			Node target = e.target();
			
			OntoEle sourceEle = (OntoEle) cmg.getNodeValue(source);
			OntoEle targetEle = (OntoEle)cmg.getNodeValue(target);
			
			if(sourceEle.getName().equalsIgnoreCase(headNodeLabel) || targetEle.getName().equalsIgnoreCase(headNodeLabel))
				ans.add(e);
		}
		
		
		return ans;
	}
	
	public static Node getNodeCorrespondingLabel(Edge incidentEdge, String headNodeLabel, ValuedGraph cmg){
		
		Node ans = incidentEdge.source();
		
		OntoEle ele = (OntoEle) cmg.getNodeValue(ans);
		
		if(ele.getName().equalsIgnoreCase(headNodeLabel))
			return ans;
		
		return incidentEdge.target();
		
	}
	
	
	public static double getConditionalProbability(HashMap<ArrayList<String>, OntoPath> pairToPaths, EdgeList steiner, FormTree tree, ValuedGraph cmg, EdgePriors priors, 
			ArrayList<ArrayList<EdgeGivenPath>> likelihoods){
		 
		
		System.out.println("Computing conditional probability for a candidate steiner tree.");
		
		Iterator<ArrayList<String>> outerIt = pairToPaths.keySet().iterator();
		
		double prob = 0.0;
		
		while(outerIt.hasNext()){
			//the outer summation
			
			ArrayList<String> outerPair = outerIt.next();
			
			//get a path
			OntoPath aPath = pairToPaths.get(outerPair);
			
			ArrayList<EdgeGivenPath> likelihoodvalues = null;
			
			boolean found = false;
			for(ArrayList<EdgeGivenPath> values: likelihoods){
				EdgeGivenPath aValue = values.get(0);
				OntoPath aValuePath = aValue.getPath();
				if (aValuePath == null) //assume that this path represents all the 
					//other paths which don't appear in the training data
					likelihoodvalues = values;
				else if(isSamePath(aPath, aValuePath)){//find the path appearing in training data
					likelihoodvalues = values;
					found = true;
					break;
				}
			}
			
			if(!found){//this aPath didn't appear in the training data
				EdgeGivenPath notAppearingPath = likelihoodvalues.get(0);
				double conditionalProbForNotAppearingPath = notAppearingPath.getConditionalProb();
				//accumulate the conditional probability of paths which didn't appear in the training data
				prob += conditionalProbForNotAppearingPath * pairToPaths.size();
			}
			else{
				
				Iterator<ArrayList<String>> innerIt = pairToPaths.keySet().iterator();
				while(innerIt.hasNext()){//inner loop over each pair of nodes (each edge)
					ArrayList<String> innerPair = innerIt.next();
					double aConditionalProb = getConditionalProbPairGivenPath(innerPair, likelihoodvalues, cmg);
					prob += aConditionalProb;
				}			
			}
			
			
			//get the set of edges in the path; accumulate
			ArrayList<Edge> edges = aPath.getEdgePath();
			for(Edge edge: edges){
				if(priors.get(edge) != null)
					prob += priors.get(edge).doubleValue();
				else
					prob += priors.getDummyPrior();
			}
			
		}
		
		
		return prob;
	}
	
	
	public static boolean isSamePath(OntoPath aPath, OntoPath aValuePath){
		
		boolean ans = true;
		
		ArrayList<Edge> aPathEdges = aPath.getEdgePath();
		ArrayList<Edge> aValuePathEdges = aValuePath.getEdgePath();
		
		for(Edge e: aPathEdges)
			if(!aValuePathEdges.contains(e))
				return false;
		
		for(Edge e: aValuePathEdges)
			if(!aPathEdges.contains(e))
				return false;
		
		return ans;
		
	}
	
	
	/**
	 * 
	 * return the conditional probability matching the pair of node labels.
	 * 
	 * @param innerPair
	 * @param likelihoodvalues
	 * @return
	 */
	public static double getConditionalProbPairGivenPath(ArrayList<String> innerPair, ArrayList<EdgeGivenPath> likelihoodvalues,
			ValuedGraph cmg){
		
		double ans = 0.0;
		
		for(EdgeGivenPath edge: likelihoodvalues){
			
			OntoNodePair pair = edge.getEdge();
			
			if(pair.getFirstNode() == null || pair.getSecondNode() == null)//for all the not matching edges
				ans = edge.getConditionalProb();
			else{
				if(isMatching(innerPair, pair, cmg)){//found a matching edge
					ans = edge.getConditionalProb();
					break;
				}
				
			}
			
		}
		
		return ans;
	}
	
	//check wether the pair of node labels match the pair of nodes
	public static boolean isMatching(ArrayList<String> innerPair, OntoNodePair pair, ValuedGraph cmg){
		
		boolean ans = false;
		
		Node firstNode = pair.getFirstNode();
		Node secondNode = pair.getSecondNode();
		
		String firstNodeLabel = ((OntoEle)cmg.getNodeValue(firstNode)).getName();
		String secondNodeLabel = ((OntoEle)cmg.getNodeValue(secondNode)).getName();
		
		if((innerPair.get(0).equalsIgnoreCase(firstNodeLabel) && innerPair.get(1).equalsIgnoreCase(secondNodeLabel)) ||
				(innerPair.get(0).equalsIgnoreCase(secondNodeLabel) && innerPair.get(1).equalsIgnoreCase(firstNodeLabel)))
			ans = true;
		
		
		return ans;
	}

}
